package com.lht.leetcodeDemo;

import org.junit.Test;

/**
 * <p>
 *     牛顿迭代实现平方根
 * </p>
 * @author Eric
 * @version 1.0
 * @date 2019-05-23
 */
public class MySqart {

    @Test
    public void testMySqart(){
        MySqart sqart=new MySqart();

        System.out.println(sqart.mySqart(2147483647));
    }
    /**
     * <p>
     *     牛顿迭代公式
     *     x=x- f(x)/f`(x)
     *     f`(x) 是f(x) 导数
     *     f(x)=x*x-a  导函数是 f`(x)=2x
     *
     *     x=x- (x*x-a)/2x
     *      =2x*x/2x  - x*x-a/2x
     *      =(x-a/x)/2
     *      这里a可以是任意数
     * </p>
     * @author Eric
     * @date 2019/5/23
     * @param x 1
     * @return int
     * @throws
     **/
    public int mySqart(int x){
        //r 是要求的解，x是 a 随机定义的常量
        Long r=Long.valueOf(x);
        while(r*r>x){
            r=(r+x/r)/2;
        }
        return r.intValue();
    }
    /**
     * <p>
     *     r = 0x5f3759df - (r >> 1);
     *     这步看不懂 ，就是快
     * </p>
     * @author Eric
     * @date 2019/5/23
     * @param x 1
     * @return int
     * @throws
     **/
    public int fastSqart(int x){
        long r=x;
        r = 0x5f3759df - (r >> 1);
        while(r*r>x){
            r=(r+x/r)/2;
        }
        return (int)r;
    }
}
